package LeetCode;

public class PalindromePartitioning2
{
  //pass both
  //pos(i)(j)=true if s(i)==s(j) && pos(i+1)(j-1)
  //dp(i)=min(1+dp(j+1) if s(i,j) is palindrome, j from i until n)
  public int minCut(String s) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int n = s.length();
    boolean[][] pos = new boolean[n][n];
    int[] dp = new int[n+1];
    for(int i = 0; i < n+1; i++){
      dp[i] = n-i;
    }
    
    for(int i = n - 1; i >= 0; i--){
      for(int j = i; j < n; j++){
        if(s.charAt(i) == s.charAt(j) && ((j - i) < 2 || pos[i+1][j-1])){
          pos[i][j]=true;
          dp[i]=Math.min(dp[i], 1+dp[j+1]);
        }
            
      }
    }
    return dp[0]-1;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    PalindromePartitioning2 p = new PalindromePartitioning2();
    System.out.println(p.minCut("cabababcbc"));
  }

}
